package www.study.com;

import java.util.Stack;

//最长有效括号 https://leetcode.cn/problems/longest-valid-parentheses/
public class code32 {
    public static void main(String[] args) {

    }

    class Solution {
        public int longestValidParentheses(String s) {
            if(s == null || s.length() <= 1) return 0;
            Stack<Integer> stack = new Stack<>(); //栈顶元素记录，上一个没有被匹配的}的位置
            stack.push(-1);
            int ans = 0;
            for(int i = 0 ; i < s.length() ; i++){
                if(s.charAt(i) == '('){
                    stack.push(i);
                }else{
                    stack.pop();
                    if(stack.isEmpty()){
                        stack.push(i);
                    }else{
                        int topNum = stack.peek();
                        ans = Math.max(ans, i - topNum);
                    }
                }
            }
            return ans;
            // if(s == null || s.length() <= 1) return 0;
            // int res = 0; //result
            // int cnt = 0; //模拟栈，记录'('个数
            // int tmp = 0;
            // for(int i = 0 ; i < s.length() ; i++){
            //     if(s.charAt(i) == '('){
            //         cnt++;
            //         //tmp++;
            //     }else{
            //         if(cnt != 0){
            //             cnt--;
            //             tmp += 2;
            //         }else{
            //             //从此处开始非法
            //             res = Math.max(res,tmp);
            //             tmp = 0;
            //         }
            //     }
            // }
            // res = Math.max(res,tmp);
            // return res;
        }
    }
}
